package oj.oj_771;

/**
 * 771. 宝石与石头
 */

import java.util.*;

public class Solution {
    // O((M + N) * Log(M))
    // jewels.length : M
    // stones.length : N
    public int numJewelsInStones(String jewels, String stones) {
        // 先构建宝石集合
        TreeSet<Character> jewelSet = new TreeSet<>();
        // 将每一种宝石都放到 Set 中
        // 先遍历 jewels String -> char
        // toCharArray()   i s.charAt(i)
        // O(M * log(M))
        for (char ch : jewels.toCharArray()) {  // M
            jewelSet.add(ch);                   // log(M)
        }

        // 拿着每一块石头去宝石集合中搜索
        int ans = 0;
        // O(N * log(M))
        for (char sto : stones.toCharArray()) {   // N
            if (jewelSet.contains(sto) == true) {   // log(M)
                ans++;
            }
        }

        return ans;
    }
}

